package swordoffer.offer36;

public class Solution {
    // head节点用于最终返回双向链表的头节点
    Node head = null;
    // pre 表示当前节点的前一个节点
    Node pre = null;

    public Node treeToDoublyList(Node root) {
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }

    // 递归中序遍历
    public void dfs(Node root) {
        // base case : 越过叶子结点返回
        if (root == null) {
            return;
        }
        dfs(root.left);
        // 先找到最左边的节点，为链表的头节点
        if (head == null) {
            head = root;
        } else if (pre != null) {   // 当前驱节点存在时，修改引用的指向
            pre.right = root;
            root.left = pre;
        }
        // 记录前驱节点
        pre = root;
        dfs(root.right);
    }
}
